This invention relates to information storage and retrieval systems, and more particularly to means for encoding and decoding codewords for use in error detection and correction in such information storage and retrieval systems.
Digital information storage devices, such as magnetic disk, magnetic tape or optical disk, store information in the form of binary bits. Also, information transmitted between two digital devices, such as computers, is transmitted in the form of binary bits. During transfer of data between devices, or during transfer between the magnetic or optical media and the control portions of a device, errors sometimes occur. Errors can also be caused by defects in the magnetic or optical storage medium. These errors must be corrected if the storage device is to be useful.
Correction of this information is accomplished by deriving additional bits of information, called check bits or redundancy, by processing the data mathematically; appending the check bits to the original data bits during the storage process; and reprocessing the data and check bits mathematically to detect and correct erroneous data bits at the time the information is retrieved. The process of deriving the check bits is called encoding and one class of codes often used in the process of encoding is Reed-Solomon codes.
Encoding of error correction information is accomplished by processing a set of n data bits, called a data block, to devise a set of r check bits, in accord with an encoding rule such as one of the Reed-Solomon codes. An encoder processes the data bock with the encoding rule to create the r check bits and then appends the check bits to the data block to form a codeword which is transmitted over the signal channel or stored in an information storage device. When the codeword is received from the signal channel or read from the storage device, a decoder processes the codeword to detect the presence of error(s) and to correct any error(s) present before transferring the data bits for further processing.
Symbol-serial encoders for Reed-Solomon error correcting codes are known in the prior art (see Riggle, U.S. Pat. No. 4,413,339). These encoders utilize the conventional or standard finite field basis but are not easy to adapt to bit-serial operation. Bit-serial encoders for Reed-Solomon codes are also known in the prior art (see Berlekamp, U.S. Pat. No. 4,410,989), however, such encoders are based on the finite field dual basis representation. Because these bit-serial encoders use the dual basis representation, mapping circuitry is required when they are utilized in a Reed-Solomon code application where the code has been defined with the conventional or standard representation of a finite field.
It is thus apparent that there is a need in the art for an encoding system that uses the conventional or standard basis, and which is suitable for bit-serial operation within an information storage device.